package sort;

import java.util.Arrays;
import java.util.Random;

/**
 * Created With IntelliJ IDEA.
 * Descriptions:
 * User:Mr.Du
 * Date:2022/3/8
 * Time:16:25
 */
public class MergeSort {

    public static void main(String[] args) {
        int[] arr = new int[10];
        Random r = new Random();

        for(int j = 0;j<10;j++){
            for(int i = 0;i<arr.length;i++){
                arr[i] = r.nextInt(50);
            }
            System.out.println("原数组: ");
            System.out.println(Arrays.toString(arr));
            mergeSort(arr,0,arr.length-1);
            System.out.println("归并排序后的数组: ");
            System.out.println(Arrays.toString(arr));
        }
    }



    private static void mergeSort(int[] arr, int start, int end) {
        if(start>=end) return;
        int mid = (end - start) / 2 + start;
        mergeSort(arr,start,mid);
        mergeSort(arr,mid+1,end);
        mergeSortTrue(arr,start,mid,end);
    }

    private static void mergeSortTrue(int[] arr, int start, int mid, int end) {
        int i = start;
        int j = mid+1;
        int[] tmp = new int[end - start + 1];
        int index = 0;
        while(i<=mid&&j<=end){
            if(arr[i]>arr[j]){
                tmp[index++] = arr[j++];
            }else{
                tmp[index++] = arr[i++];
            }
        }
        int low = i;
        int high = mid;
        if(j<=end){
            low = j;
            high = end;
        }
        while(low<=high){
            tmp[index++] = arr[low++];
        }
        System.arraycopy(tmp,0,arr,start,tmp.length);
    }
}
